package com.gxc.heap;

import java.util.HashMap;

/**
 * 自定义词频堆
 *
 * 设计并实现TopKRecord结构，可以不断地向其中加入字符串，
 * 并且可以根据字符串出现的情况随时打印加入次数最多的前k个字符串。
 * 具体为:
 * 1)k在TopKRecord实例生成时指定，并且不再变化(k是构造TopKRecord的参数)
 * 2)含有 add(String str)方法，即向TopKRecord中加入字符串。
 * 3)含有 printTopK()方法，即打印加入次数最多的前k个字符串，打印有哪些字符串和对应的次数即可，不要求严格按排名顺序打印。
 * 4)如果在出现次数最多的前k个字符串中，最后一名的字符串有多个，比如出现次数最多的前3个字符串具体排名为:
 * A 100次 B 90次 C 80次 D 80次 E80次，其他任何字符串出现次数都
 * 不超过80次
 * 那么只需要打印3个，打印ABC、ABD、ABE都可以。也就是说可以随意抛弃最后一名，只要求打印k个
 * 要求:
 * 1)在任何时候，add 方法的时间复杂度不超过 0(logk)
 * 2)在任何时候，printTopK方法的时间复杂度不超过0(k)
 */
public class CustomWordFrequencyHeap {

    public static void main(String[] args) {
        System.out.println(-1 / 2);
    }

    /**
     * 堆数组
     */
    public WordFrequency[] heap;
    /**
     * 堆中有元素的大小
     */
    public int index;
    /**
     * string 词频map
     */
    public HashMap<String, WordFrequency> strTimesMap;
    /**
     * string 在堆中坐标map
     */
    public HashMap<WordFrequency, Integer> strIndexMap;

    /**
     * 堆初始化
     * @param size
     */
    public CustomWordFrequencyHeap(int size) {
        heap = new WordFrequency[size];
        index = 0;
        strTimesMap = new HashMap<>();
        strIndexMap = new HashMap<>();
    }

    /**
     * 堆添加元素
     * @param str
     */
    public void addString(String str) {
        WordFrequency cur = null;
        //是否在堆上，如果 preIndex = -1 ，则元素不在堆中
        int preIndex = -1;
        //如果是首次添加
        if (!strTimesMap.containsKey(str)) {
            cur = new WordFrequency(str, 1);
            strTimesMap.put(str, cur);
            strIndexMap.put(cur, -1);
        } else {
            cur = strTimesMap.get(str);
            cur.times++;
            preIndex = strIndexMap.get(cur);
        }

        if (preIndex == -1) {
            //如果当前堆中元素没满
            if (index < heap.length) {
                strIndexMap.put(cur, index);
                heap[index] = cur;
                heapInsert(index++);
                //如果当前堆中元素已满,且当前元素的词频大于堆头元素，则替换堆顶，
            } else {
                if (cur.times > heap[0].times) {
                    strIndexMap.put(heap[0], -1);
                    strIndexMap.put(cur, 0);
                    heap[0] = cur;
                    heapify(0, index);
                }
            }
        } else {
            heapify(preIndex, index);
        }
    }

    /**
     * 元素属性变更后向下排序
     * @param index
     * @param heapSize
     */
    private void heapify(int index, int heapSize) {
        int left = 2*index + 1;

        int small = index;
        while (left < heapSize) {
            //先比较子节点大小
            small = left+1 < heapSize && heap[left].times > heap[left+1].times ? left+1 : left;
            small = heap[index].times > heap[small].times ? small : index;
            if (small == index) break;

            swap(index, small);
            index = small;
            left = 2 * index +1;
        }
    }

    /**
     * 在尾部插入新元素后向上排序
     * @param index
     */
    private void heapInsert(int index) {
        //小根堆，比较inde 和 parent
        while (heap[index].times < heap[(index-1)/2].times) {
            swap(index, (index-1)/2);
            index = (index-1)/2;
        }
    }

    private void swap(int source, int target) {
        //交换堆中元素
        WordFrequency temp = heap[source];
        heap[source] = heap[target];
        heap[target] = temp;
        //交换堆位置map中位置
        strIndexMap.put(heap[source], target);
        strIndexMap.put(heap[target], source);
    }

    public void printTopK() {
        System.out.println("TOP:");
        for (int i = 0; i < heap.length; i++) {
            WordFrequency wordFrequency = heap[i];
            if (wordFrequency ==null) break;
            System.out.println(wordFrequency.str + ":" + wordFrequency.times);
        }
    }

}
